#include "headfiles.h"

using namespace std;

static int compareString(const char *str1, const char *str2) {
    size_t str1_len = strlen(str1);
    size_t str2_len = strlen(str2);

    if (str1_len > str2_len) {
        return 1;
    }
    else if (str1_len == str2_len) {
        return 0;
    }
    else {
        return -1;
    }
}

static void quickSortString(const char **array, int start, int end) {
    // If only 1 or less element is available, return
    if (start >= end - 1) {
        return;
    }

    int l = start + 1;
    int index = start;
    int r = end - 1;

    int pivot_loc = (start + end) / 2;
    const char *pivot_str = array[pivot_loc];
    array[pivot_loc] = array[start];

    while (l <= r) {
        int ret = compareString(array[l], pivot_str);
        if (ret >= 0) {
            array[index] = array[l];
            ++index;
            ++l;
        }
        else {
            const char *str_tmp = array[l];
            array[l] = array[r];
            array[r] = str_tmp;
            --r;
        }
    }
    array[index] = pivot_str;

    quickSortString(array, start, index);
    quickSortString(array, index + 1, end);

    return;
}


static bool sortString(const char **str_array, int n) {
    if (str_array == NULL ||
        n <= 0) {
        cout << "Invalid input arguments!" << endl;
        return false;
    }

    quickSortString(str_array, 0, n);

    return true;
}


bool stringCombination(const char **str_array, int n) {

    //Sort all the string in the descending order
    sortString(str_array, n);    

    int i, j;
    const char *match_ptr, *start_ptr;
    for (i = 0; i < n; i++) {
        cout << "size = " << strlen(str_array[i]) << ", " << str_array[i] << endl;
    }

    // For the first word, check all the combinations to see
    // if there is a match for anyone.
    int match_size, total_match_size;
    vector<int> word_vec;
    for (i = 0; i < n; i++) {
        start_ptr = str_array[i];
        word_vec.clear();
        total_match_size = strlen(start_ptr);
        match_size = 0;
        while (match_size < total_match_size) {
            bool match_flag = false;
            for (j = i + 1; j < n; j++) {
                match_ptr = strstr(start_ptr, str_array[j]);
                if (match_ptr == start_ptr) {
                    start_ptr += strlen(str_array[j]);
                    match_size += strlen(str_array[j]);
                    word_vec.push_back(j);
                    match_flag = true;
                    break;
                }
            }

            // No match for the remaining subword, search the next word
            if (match_flag == false) {
                break;
            }

            // If the total search lenght equal to the word to be searched
            if (match_size == total_match_size) {
                cout << str_array[i] << " consists of:" << endl;
                vector<int>::iterator it;
                for (it = word_vec.begin(); it != word_vec.end(); it++) {
                    cout << str_array[*it] << "\t";
                }
                cout << endl;

                // The first one matched is the longest one
                return true;
            }
        }
    }

    return true;
}

